# Хеш-таблицы

Структура данных, использующая метод сопоставления больших диапазонов с меньшими, называется хеш-таблицей.
Она хранит ключи и их значения, используя хэш-функцию для сопоставления. 
Хеш-таблица — это одна из наиболее эффективных структур данных со временем выполнения _O(1)_ для поиска, вставки и удаления. 
В худшем случае, особенно когда связанные списки хранятся как значения, время выполнения может быть _O(n)_.

С точки зрения структуры хеш-таблица больше похожа на массив; однако способ обращения к элементам отличается. 
В массиве элементы адресуются с использованием прямой адресации. 
При прямой адресации доступ к элементу в позиции k осуществляется с использованием значения индекса k. 
В хеш-таблицах ключи вычисляются с помощью хэш-функции. 
Суть хеш-таблицы заключается в возможности разработать хэш-функцию, 
которая эффективно отображает реальный или проблемный диапазон и диапазон, доступный (или выделенный) в компьютере. 
Хорошая хэш-функция может равномерно распределять реальные ключи в памяти компьютера без каких-либо коллизий. 
Коллизия возникает, когда два или более реальных ключа сопоставляются с одним ключом хеш-таблицы. 
Когда ключи проблемного пространства имеют очень большой диапазон, 
может оказаться невозможным иметь уникальные соответствующие ключи в хеш-таблице. 
В таких сценариях связанные списки используются для обеспечения дополнительной идентификации. 
Помимо ключа, можно сравнивать значения объектов. 
В таких реализациях в худшем случае поиск элемента в хэш-таблице может занять время _O(n)_. 
Это в первую очередь потому, что задействованы связанные списки.


---

**Ссылки:**

- [Bhim P. Upadhyaya - Data Structures and Algorithms with Scala](https://link.springer.com/book/10.1007/978-3-030-12561-5)
